import java.util.Arrays;

public class SolutionInterview17_8 {
    public int bestSeqAtIndex(int[] height, int[] weight) {
        int[][] envelopes=new int[height.length][2];
        for (int i=0;i<height.length;i++){
            envelopes[i][0]=height[i];
            envelopes[i][1]=weight[i];
        }
        Arrays.sort(envelopes, (a, b)->a[0]==b[0]?b[1]-a[1]:a[0]-b[0]);
        int[] f=new int[envelopes.length+1];
        int len=0;
        for (int[] envelope : envelopes) {
            if (envelope[1] > f[len]) {
                len++;
                f[len] = envelope[1];
            } else {
                int l = 1, r = len, t = -1;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (f[mid - 1] < envelope[1] && envelope[1] <= f[mid]) {
                        t = mid;
                        break;
                    } else if (envelope[1] > f[mid]) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                f[t] = envelope[1];
            }
        }
        return len;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionInterview17_8().bestSeqAtIndex(new int[]{65,70,56,75,60,68},new int[]{100,150,90,190,95,110}));
    }
}
